Complejidad temporal

En informática, la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que lleva ejecutar un algoritmo. La complejidad temporal se estima comúnmente contando el número de operaciones elementales realizadas por el algoritmo, suponiendo que cada operación elemental requiere una cantidad fija de tiempo. Por lo tanto, la cantidad de tiempo necesario y el número de operaciones elementales realizadas por el algoritmo difieren en un factor constante como máximo.

Dado que el tiempo de ejecución de un algoritmo puede variar entre diferentes entradas del mismo tamaño, comúnmente se considera la complejidad temporal del peor caso, que es la cantidad máxima de tiempo requerida para las entradas de un tamaño determinado. Menos común, y usualmente especificado explícitamente, es la complejidad del caso promedio, que es el promedio del tiempo necesario para las entradas de un tamaño dado (esto tiene sentido porque solo hay un número finito de entradas posibles de un tamaño dado). En ambos casos, la complejidad temporal generalmente se expresa como una función del tamaño de la entrada.^[1]​ Dado que esta función es generalmente difícil de calcular exactamente, y el tiempo de ejecución para entradas pequeñas generalmente no es consecuente, uno comúnmente se enfoca en el comportamiento de la complejidad cuando aumenta el tamaño de entrada, es decir, el comportamiento asintótico de la complejidad. Por lo tanto, la complejidad temporal se expresa comúnmente usando la notación O grande, típicamente ${\displaystyle O(n)}$, ${\displaystyle O(n\log n)}$, ${\displaystyle O(n^{\alpha })}$, ${\displaystyle O(2^{n})}$, etc., donde n es el tamaño de entrada en unidades de bits necesarios para representar la entrada.

Las complejidades algorítmicas se clasifican según el tipo de función que aparece en la notación O grande. Por ejemplo, un algoritmo con complejidad temporal ${\displaystyle O(n)}$ es un algoritmo de tiempo lineal y un algoritmo con complejidad de tiempo ${\displaystyle O(n^{\alpha })}$ por alguna constante ${\displaystyle \alpha >1}$ es un algoritmo de tiempo polinómico .

1. ↑ Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.